package com.yubest;

/**
 * 基于位的加、减、乘、除
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/12/8 10:12
 */
public class BitCalculation {

    public static void main(String[] args) {
        System.out.println(new BitCalculation().add(11, -10));

        System.out.println(new BitCalculation().sub(2, 8));

        System.out.println(new BitCalculation().mul(-2, -11));

        System.out.println(new BitCalculation().div(8, 2));

    }

    /**
     * 加
     *
     * 设a，b为两个二进制数，则 a + b = a ^ b + (a & b) << 1
     *
     * @param a
     * @param b
     * @return
     */
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        //a ^ b : 不进位相加
        //(a & b) << 1 : 进位
        return add(a ^ b, (a & b) << 1);
    }

    public int sub(int a, int b) {
        //a减b，其实就是a加负b。
        //先求负b，求一个数的负的操作是将其连符号位一起取反然后加1
        return add(a, negative(b));
    }

    //注意：没有处理 Integer.MIN_VALUE 的情况
    private int negative(int n) {
        //负n，就是将其连符号位一起取反然后加1
        return add(~n, 1);
    }

    private int abs(int n) {
        return n < 0 ? negative(n) : n;
    }

    /**
     * 乘
     *
     * 示例：
     *            1 0 0 1
     *         x  0 1 1 0
     *  -------------------
     *           0 0 0 0
     *         1 0 0 1
     *       1 0 0 1
     *  +  0 0 0 0
     *  -------------------
     *     0 1 1 0 1 1 0
     *
     * @param a
     * @param b
     * @return
     */
    public int mul(int a, int b) {
        //判断最终的结果是正是负
        //将原数往右移31位，即得到原数对应的符号位，判断符号位是否相同，不同则结果为负；相同则结果为正
        boolean isNegative = (a >> 31) != (b >> 31);
        //a取绝对值
        a = abs(a);
        //b取绝对值
        b = abs(b);
        int r = 0;
        while (b != 0) {
            if ((b & 1) == 1) {
                r = add(r, a);
            }
            a <<= 1;
            b >>= 1;
        }
        return isNegative ? negative(r) : r;
    }

    /**
     * 除
     *
     * 注意：没有处理 b = 0 和 Integer.MIN_VALUE 的情况
     *
     * @param a
     * @param b
     * @return
     */
    public int div(int a, int b) {
        //判断最终的结果是正是负
        //将原数往右移31位，即得到原数对应的符号位，判断符号位是否相同，不同则结果为负；相同则结果为正
        boolean isNegative = (a >> 31) != (b >> 31);
        //a取绝对值
        a = abs(a);
        //b取绝对值
        b = abs(b);
        int r = 0;
        int i = 31;
        while (i >= 0) {
            if ((a >> i) >= b) {
                r = add(r, 1 << i);
                a = sub(a, b << i);
            }
            i = sub(i, 1);
        }
        return isNegative ? negative(r) : r;
    }
}
